import java.util.ArrayList;
import java.util.List;

/**
 * 
 * 完全背包
 * 
 * 
 * 题目

有N种物品和一个容量为V的背包，每种物品都有无限件可用。第i种物品的费用是w[i]，价值是v[i]。求解将哪些物品装入背包可使这些物品的费用总和不超过背包容量，且价值总和最大。

基本思路

这个问题非常类似于01背包问题，所不同的是每种物品有无限件。也就是从每种物品的角度考虑，与它相关的策略已并非取或不取两种，而是有取0件、取1件、取2件……等很多种。如果仍然按照解01背包时的思路，令dp[i][j]表示前i种物品恰放入一个容量为v的背包的最大权值。仍然可以按照每种物品不同的策略写出状态转移方程，像这样：



 * 
 */

public class 完全背包 {

    private static int bagWeight = 8;
    private static List<BagInfo> goodsList = new ArrayList<>();
    
    public static void main(String[] args) {
        

        goodsList.add(new BagInfo(0, 0));
        goodsList.add(new BagInfo(2, 3));
        goodsList.add(new BagInfo(3, 4));
        goodsList.add(new BagInfo(4, 5));
        goodsList.add(new BagInfo(5, 6));

        System.out.println(""+completeKnapsack(goodsList, bagWeight));


    }


    //N为物品数量
    //W为背包总体积
    //weights[]为每个物品的体积
    //values[]为每个物品的价值
    
    private static int completeKnapsack(List<BagInfo> bags, int cap){
        
        int n = bags.size();
        // 初始化 dp 表
        int[][] dp = new int[n + 1][cap + 1];
        // 状态转移
        for (int i = 1; i <= n; i++) {
            for (int c = 1; c <= cap; c++) {
                if (bags.get(i - 1).weight > c) {
                    // 若超过背包容量，则不选物品 i
                    dp[i][c] = dp[i - 1][c];
                } else {
                    // 不选和选物品 i 这两种方案的较大值
                    dp[i][c] = Math.max(dp[i - 1][c], dp[i][c - bags.get(i - 1).weight] + bags.get(i - 1).value);
                }
            }
        }
        return dp[n][cap];
    }

    private static class BagInfo{

        public int weight;
        public int value;

        public BagInfo(int weight, int value){

            this.weight = weight;
            this.value = value;
        }
    }
}
